package 学习;

import java.util.Arrays;

/**
 * Keafmd
 *
 * @ClassName: StraghtInsertSort
 * @Description: 插入排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:36
 */
public class InsertSort {
    //插入排序
    public static void insertSort(int[] arr) {
        insertSort(arr, true);//默认进行升序
    }

    public static void insertSort(int[] arr, boolean ascending) {

        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j; //这就是那个合适的位置
            for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
                arr[j + 1] = arr[j];
            }
            //把牌放下，为啥是j+1，
            //是因为上面的循环遍历到不符合情况的时候 j是合适的位置的前面的那个数的位置
            //有点拗口，但是就是这个意思，看图方便理解下
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;
        //测试插入排序
        System.out.println("测试插入排序:");
        temparr = nums.clone();
        InsertSort.insertSort(temparr);
        //逆序排序
        //InsertSort.insertSort(temparr,false);
        System.out.println(Arrays.toString(temparr));
    }
}